package blue_bridge_cup_learning.整数划分;

// 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
// 小明一共有 N 块巧克力，其中第 i 块是 H i×W i 的方格组成的长方形。为了公平起见，
// 小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
// 形状是正方形，边长是整数;
// 大小相同;
// 例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
// 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
import java.util.*;

public class 分巧克力 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 数据初始化
        int chocolate_count = sc.nextInt();
        int k = sc.nextInt();
        int[] h = new int[chocolate_count + 1];
        int[] w = new int[chocolate_count + 1];
        for (int i = 1; i <= chocolate_count; i++) {
            h[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int l = 1, r = 100000;
        // 二分查找
        while (l < r) {
            int mid = l + r >> 1;
            // 如果分成变长为mid的巧克力，看是否满足>=k这个条件
            // 如果满足那么说明还可以再分大一点所以l=mid
            // 如果不满足那么说明不能分那么大所以r=mid-1
            if (check(h, w, chocolate_count, mid, k)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        System.out.println(l);
    }

    // 计算分成边长为size的巧克力是否满足>=k这个条件
    public static boolean check(int[] h, int[] w, int chocolate_count, int size, int k) {
        int count = 0;
        for (int i = 1; i <= chocolate_count; i++) {
            // 计算方法：巧克力长除以边长，宽除以边长，然后相乘
            count += h[i] / size * w[i] / size;
            if (count >= k) {
                return true;
            }
        }
        return false;
    }
}
